package bishi.kaizi;

import java.util.*;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2022/03/05 15:57
 */
public class kaizi {
    public static void main(String[] args) {
        kaizi kaizi = new kaizi();
//        System.out.println(kaizi.count(new ArrayList<String>() {{
//            add("((()))()");
//            add("(())");
//        }}));
        System.out.println(kaizi.validPath(4, new ArrayList<ArrayList<Integer>>() {{
            add(new ArrayList<Integer>() {{
                add(0);
                add(1);
            }});
            add(new ArrayList<Integer>() {{
                add(1);
                add(3);
            }});
            add(new ArrayList<Integer>() {{
                add(2);
                add(3);
            }});
            add(new ArrayList<Integer>() {{
                add(3);
                add(0);
            }});
        }}, 0, 2));
    }

    public int count(ArrayList<String> arr) {
        int res = 0;
        for (String str : arr) {
            str = str.replace(" ", "");
            if (str.equals("")) continue;

            int left = 0;
            char[] chars = str.toCharArray();
            boolean error = false;
            for (char c : chars) {
                if (c == '(') {
                    left++;
                } else if (left == 0) {
                    error = true;
                    break;
                } else {
                    left--;
                }
            }
            res += (error || left != 0) ? 0 : 1;
        }
        return res;
    }

    public boolean validPath(int n, ArrayList<ArrayList<Integer>> sides, int start, int end) {
        boolean[] isOk = new boolean[n];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (ArrayList<Integer> l : sides) {
            if (!map.containsKey(l.get(0))) {
                map.put(l.get(0), new HashSet<Integer>() {{
                    add(l.get(1));
                }});
            } else {
                map.get(l.get(0)).add(l.get(1));
            }
        }
        isOk[start] = true;
        if (!map.containsKey(start)) return false;
        return dfs(start,isOk,map,end);
    }
    public boolean dfs(int now,boolean[] isOk,Map<Integer, Set<Integer>> map,int end){
        Set<Integer> set = map.get(now);
        boolean nowRes = false;
        for (Integer nnow:set){
            if (isOk[nnow]) continue;
            isOk[nnow] = true;
            if (nnow==end)return true;
            else if (!map.containsKey(nnow))continue;
            else{
                nowRes = nowRes|dfs(nnow,isOk,map,end);
            }
            if (nowRes) return nowRes;
        }
        return nowRes;
    }





}
